# 90.子集II
# 给你一个整数数组nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）
# 解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。
#
# 示例1：
# 输入：nums = [1, 2, 2]
# 输出：[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
#
# 示例2：
# 输入：nums = [0]
# 输出：[[], [0]]


class Solution:
    def subsetsWithDup(self, nums: [int]):
        # 这里其实应该是用树枝去重和树层去重的，sort方法只能规避，可能会超时
        nums.sort()
        res = []
        path = []

        def backtracking(nums, index):
            tmp = path[:]
            if tmp not in res:
                res.append(tmp)
            if index == len(nums):
                return
            for i in range(index, len(nums)):
                path.append(nums[i])
                backtracking(nums, i + 1)
                path.pop()
        backtracking(nums, 0)
        return res

if __name__ == '__main__':
    nums = [1, 2, 2]
    tmp = Solution()
    res = tmp.subsetsWithDup(nums)
    print(res)